package hot100;

public class Solution1319 {

    public int makeConnected(int n, int[][] connections) {
        UnionFind unionFind = new UnionFind(n);
        for (int i = 0; i < connections.length; i++) {
            unionFind.union(connections[i][0], connections[i][1]);
        }
        return unionFind.count;

    }

    class UnionFind {

        private int[] parent;

        private int count;

        public UnionFind(int n) {
            parent = new int[n];
            count = n;
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }

        public int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        public void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX == rootY) {
                return;
            }
            parent[rootX] = rootY;
            count--;
        }
    }

    public static void main(String[] args) {
        Solution1319 solution1319 = new Solution1319();
        solution1319.makeConnected(6, new int[][] {{0,1}, {0,2}, {0,3}, {1,2}});
    }

}
